package 动态规划.经典动态规划题目.背包问题;

/**
 * 0-1 背包一个物品只能用一次
 */
/*
题目：
有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。
其中第i个物品的的重量为wt[i]，价值为val[i]。现在你用这个背包装物品，最多能装的价值是多少？
 */
public class 零一背包基础版 {


    /**
     * @param W   背包总体积
     * @param N   物品数量
     * @param wt  数组存储 N 个物品的重量
     * @param val 数组存储 N 个物品的价值
     * @return
     */
    public int knapsack(int W, int N, int[] wt, int[] val) {
        //dp[i][w]：对于前i个物品，当前背包容量为w，这种情况下可以装的最大价值
        //base case ：已经初始化为0了
        int[][] dp = new int[N + 1][W + 1];
        for (int i = 1; i <= N; i++) {
            for (int w = 1; w < W; w++) {
                if (w - wt[i] < 0) {
                    //背包容量不够了，只能选择不放入背包
                    dp[i][w] = dp[i - 1][w];
                } else {
                    //装入或不装入背包，择优
                    dp[i][w] = Math.max(dp[i - 1][(w-wt[i - 1] )] + val[i - 1], dp[i - 1][w]);
                }
            }
        }
        return dp[N][W];
    }
}
